package weekMatch.one_345;

import java.util.*;

public class LeeCode_03 {
    public static void main(String[] args) {
        System.out.println(countCompleteComponents(6, new int[][]{{0, 1}, {0, 2}, {1, 2}, {3, 4}, {4, 5}}));
    }
    private static int countCompleteComponents(int n, int[][] edges) {
        int[] p = new int[n];
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            if (map.containsKey(edge[0])){
                map.get(edge[0]).add(edge[1]);
            }else {
                HashSet<Integer> list = new HashSet<>();
                list.add(edge[1]);
                map.put(edge[0], list);
            }
            if (map.containsKey(edge[1])){
                map.get(edge[1]).add(edge[0]);
            }else {
                HashSet<Integer> list = new HashSet<>();
                list.add(edge[0]);
                map.put(edge[1], list);
            }
        }
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
        for (int[] edge : edges) {
            union(p, edge[0], edge[1]);
        }
        Map<Integer, List<Integer>> map2 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int root = find(p, i);
            if (map2.containsKey(root)){
                map2.get(root).add(i);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map2.put(root, list);
            }
        }
        int ans = 0;
        for (Integer root : map2.keySet()) {
            List<Integer> list = map2.get(root);
            int size = list.size();
            boolean flag = true;
            for (int i = 0; i < size; i++) {
                if (!flag)
                    break;
                for (int j = i + 1; j < size; j++) {
                    int from = list.get(i);
                    int to = list.get(j);
                    if (!(map.containsKey(from) && map.get(from).contains(to))){
                        flag = false;
                        break;
                    }
                }
            }
            if (flag){
                ans++;
            }
        }
        return ans;
    }
    private static void union(int[] p, int x, int y){
        int rx = find(p, x);
        int ry = find(p, y);
        p[rx] = ry;
    }
    private static int find(int[] p, int x){
        if (p[x] == x)
            return x;
        return find(p, p[x]);
    }
}
